package com.lry.basic.algorithm.matrix;

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

class WordSearch2 {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> list = new ArrayList();

        boolean[][] visited = new boolean[board.length][board[0].length];
        for(String word:words){

            List<Point> ps = new ArrayList();
            for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    visited[i][j] = false;
                    if(board[i][j]==word.charAt(0)){
                        ps.add(new Point(i,j));
                    }
                }
            }
            boolean result = false;
            for(Point point:ps){
                result |=dfs(board,word,0,point.x,point.y,visited);
            }
            if(result){
                list.add(word);
            }
        }
        return list;
    }

    private boolean dfs(char[][] board,String word,int wordIndex,int si,int sj,boolean[][] visited){
        if(si>=board.length || si<0 || sj>=board[0].length || sj<0){
            return false;
        }
        
        if(wordIndex==word.length()-1&&word.charAt(wordIndex)==board[si][sj]&&!visited[si][sj]){
            return true;
        }
        
        if(word.charAt(wordIndex)==board[si][sj]&&!visited[si][sj]){
           visited[si][sj] = true;
           boolean result = 
           dfs(board,word,wordIndex+1,si-1,sj,visited)||
           dfs(board,word,wordIndex+1,si+1,sj,visited)||
           dfs(board,word,wordIndex+1,si,sj-1,visited)||
           dfs(board,word,wordIndex+1,si,sj+1,visited);

           visited[si][sj] = false;

           return result;
        }else{
            return false;
        }
    }


    public static void main(String[] args) {
        WordSearch2 solution = new WordSearch2();
        System.out.println(solution.findWords(new char[][]{{'a', 'b','c'},{'a','e','d'},{'a','f','g'}}, new String[]{"abcdefg","gfedcbaaa","eaabcdgfa","befa","dgc","ade"}));
    }

    
}